package algorithm;

public class T00221 {
    public static void main(String[] args) {
        char[][] matrix = {{'0','0','0','1'},{'1','1','0','1'},{'1','1','1','1'},{'0','1','1','1'},{'0','1','1','1'}};
        System.out.println(new Solution().maximalSquare(matrix));
    }

    static class Solution {
        public int maximalSquare(char[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            int[][] dp = new int[m][n];
            int max = 0;
            for (int i = 0; i < m; i ++) {
                dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
                max = Math.max(max, dp[i][0]);
            }
            for (int i = 0; i < n; i ++) {
                dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
                max = Math.max(max, dp[0][i]);
            }
            for (int i = 1;i < m;i ++) {
                for (int j = 1; j < n; j ++) {
                    if (matrix[i][j] == '1') {
                        dp[i][j] = 1;
                        if (matrix[i - 1][j] == '1' && matrix[i][j - 1] == '1')
                            dp[i][j] += min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
                    } else {
                        dp[i][j] = 0;
                    }
                    max = Math.max(max, dp[i][j]);
                }
            }
            return max * max;
        }

        private int min(int dp1, int dp2, int dp3) {
            return Math.min(dp1, Math.min(dp2, dp3));
        }
    }
}
